Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 67/115

Q: What is the space complexity of a treap algorithm?
A. O(N)
B. O(log N)
C. O(log N)
D. O(N2)
Solution: The average case and worst case space complexity of a treap is mathematically found to be O(N).
Q: A treap is a combination of a tree and a heap.
A. false
B.  true
C. 
D. 
Solution:  A treap is a combination of a tree and a heap. The structure of a treap is determined by the fact that it is heap-ordered.
Q: Which is the simplest of all binary search trees?
A. AVL tree
B. Treap
C. Splay tree
D. Binary heap
Solution: A treap is the simplest of all binary search trees. Each node is given a numeric priority and implementation is non recursive.
Q: What is the reason behind the simplicity of a treap?
A. Each node has data and a pointer
B. Each node is colored accordingly
C. It is a binary search tree following heap principles
D. Each node has a fixed priority field
Solution: A treap is the simplest of all because we don’t have to worry about adjusting the priority of a node.
Q: What is the condition for priority of a node in a treap?
A. a node’s priority should be greater than its parent
B. a node’s priority should be at least as large as its parent
C. the priority is randomly assigned and can have any value
D. a node’s priority is always given in decreasing order
Solution: A node’s priority should satisfy heap order. That is, any node’s priority should be at least as large as its parent.
Q: Several other operations like union set difference and intersection can be done in treaps.
A. True
B. False
C. 
D. 
Solution: Other than insertion, deletion and search operations, several operations like union, intersection and set difference can be done in treaps.
Q: What is the average running time of a treap?
A. O(N)
B. O(N log N)
C. O(log N)
D. O(M log N)
Solution: The average case and worst case analysis of a treap are mathematically found to be O(log N).
Q: Which node has the lowest priority in a treap?
A. root node
B. leaf node
C. null node
D. centre node
Solution: A root node has the lowest priority in a treap since the node’s priority is based on heap order.
Q: What is the priority of a null node?
A. 1
B. 0
C. random number
D. infinity
Solution: The priority of a null node is set to be infinity in a treap so that during deletion, priority of that particular node is set to infinity, rotated and freed.
Q: Who invented treaps?
A. Cecilia and Raimund
B. Arne Andersson
C. Donald Shell
D. Harris and Ross
Solution: Cecilia and Raimund invented Treaps. Arne Andersson invented AA – Trees. Donald Shell invented shell sort and Harris and Ross formulated maximum flow problem.

You Have Score    /10